/*
 * @lc app=leetcode.cn id=967 lang=c
 *
 * [967] 连续差相同的数字
 */

// @lc code=start

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
void dfs(int n, int k, int *returnSize, int len, int sum, int *ans)
{
    if (len == n)
    {
        ans[(*returnSize)++] = sum;
        return;
    }
    int lastDigit = sum % 10;
    if (lastDigit - k >= 0)
    {
        dfs(n, k, returnSize, len + 1, sum * 10 + (lastDigit - k), ans);
    }
    if (lastDigit + k < 10 && k != 0)
    {
        dfs(n, k, returnSize, len + 1, sum * 10 + (lastDigit + k), ans);
    }
    return;
}

int *numsSameConsecDiff(int n, int k, int *returnSize)
{
    int *ans = (int *)malloc(sizeof(int) * 10000);
    *returnSize = 0;
    for (int i = 1; i <= 9; i++)
    {
        dfs(n, k, returnSize, 1, i, ans);
    }
    return ans;
}
// @lc code=end
